//
// Created by Administrator on 2021/9/22.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    vector<ListNode *> splitListToParts(ListNode *head, int k) {
        if (head == nullptr) {
            vector<ListNode *> ans(k, nullptr);
            return ans;
        }
        ListNode *node = head;
        int n = 1;
        // 知道链表的总长度
        while (node->next != nullptr) {
            node = node->next;
            ++n;
        }
        int aveLen = n / k; // 平均每一段的长度
        vector<ListNode *> ans;
        for (int i = 0; i < k; ++i) {
            node = head;
            // 把一段链表放进去  需要把尾巴切掉
            ans.push_back(node);
            if (i < n % k) {
                for (int j = 0; j < aveLen; ++j) {
                    node = node->next;
                }
            } else {
                for (int j = 0; j < aveLen - 1; ++j) {
                    node = node->next;
                }
            }
            if (node != nullptr) {
                head = node->next;
                node->next = nullptr;
            } else {
                head = nullptr;
            }
        }
        return ans;
    }

};
class Solution2 {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        int n = 0;
        ListNode *temp = head;
        while (temp != nullptr) {
            n++;
            temp = temp->next;
        }
        int quotient = n / k, remainder = n % k;

        vector<ListNode*> parts(k,nullptr);
        ListNode *curr = head;
        for (int i = 0; i < k && curr != nullptr; i++) {
            parts[i] = curr;
            // 这一段链表的长度
            int partSize = quotient + (i < remainder ? 1 : 0);
            for (int j = 1; j < partSize; j++) { // 注意个数 从一开始
                curr = curr->next;
            }
            // 如果curr已经是nullptr，就会一直在这 不再走了
            ListNode *next = curr->next;
            curr->next = nullptr;
            curr = next;
        }
        return parts;
    }
};


int main() {
    ListNode n1(1), n2(2), n3(3), n4(4), n5(5), n6(6), n7(7), n8(8), n9(9), n10(10);
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    n5.next = &n6;
    n6.next = &n7;
    n7.next = &n8;
    n8.next = &n9;
    n9.next = &n10;
    Solution2 solution;
    vector<ListNode *> ans = solution.splitListToParts(&n1, 3);
    for (auto &x: ans) {
        cout << x->val << endl;
    }
    return 0;
}
